Graph analysis is a type of data analysis where the dataset is modeled as a graph. Graph analysis is used to identify arbitrary relationships between data entities. By applying certain graph analysis algorithms on a graph, a user may be able to discover non-immediate insight about the data set as analysis may consider even indirect relationships between data entities.
Many different data sets can be represented as graphs. For example, friendship relationships in a social network naturally form a graph. Real-world graphs, such as social network graphs, tend to exhibit different characteristics than classic graphs, such as trees, meshes, and hyper-cubes. As an example of a characteristic, real-world graphs show power-law degree distribution, which means that most nodes in the graph have only a small number of edges, while a few nodes have an extremely large number of edges. For example, according to the degree distribution of Twitter's follower graph, about 96% of all nodes have less than 100 edges, while about 0.01% of all nodes are connected to 25% of all edges in the graph, with roughly one hundred nodes having more than 106 edges.
Graph analysis programs are often parallelized by exploiting their inherent vertex-parallelism. In other words, a certain function is applied to every vertex in the graph in parallel. Often the “vertex function” iterates over all the edges of a vertex. Existing graph processing systems, such as GraphLab or Giraph, make use of this vertex-parallelism. Such systems maintain multiple threads (or processes) and let each thread handle a chunk of vertices at a time.
However, conventional methods of exploiting vertex-parallelism lead to serious performance issues when applied to real-world graph instances. For example, a vertex function iterates over all edges belonging to a vertex. The extreme skewedness of the degree distribution leads to poor load balancing between different threads. That is, one thread deals with the high-degree nodes and most of the other threads only deal with low-degree nodes. Such poor load balancing affects the performance of a program in a very negative way and could completely negate the positive effects of parallelizing the algorithm.
One approach to address the issue of extreme degree distribution skewedness is by applying chunking and work stealing. In this scheme, vertices (or nodes) of a graph are partitioned into multiple chunks (or sets) where each chunk has the same (or similar) number of vertices. Each thread picks up one chunk and processes the vertices belonging to the thread. When a thread finishes its chunk, the thread either grabs a new chunk or, if the work queue is empty, “steals” another chunk from another thread that still has unprocessed chunks in its respective chunk queue. Although this approach somewhat reduces the load balancing problem, it is not a perfect solution. For example, if a graph contains a “super” node to which 60% of all the nodes in the graph are connected, then the chunk that contains the super node will cause significant workload imbalance.
The approaches described in this section are approaches that could be pursued, but not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated, it should not be assumed that any of the approaches described in this section qualify as prior art merely by virtue of their inclusion in this section.